package cm.unit2.theme4;

public class MovingCount {

	public static int cnt = 0;
	public static boolean[][]check = null;
	
	public int movingCount(int threshold, int rows, int cols) {
		check = new boolean[rows][cols];
		cnt = 0;
        findPath(threshold,rows,cols,0,0);        
        return cnt;
    }

	public static void findPath(int threshold, int rows, int cols,int x,int y) {
		if(x<0 || y<0 || x>=rows || y>=cols || !checkPath(x, y, threshold)|| check[x][y]) {
    		return;
    	}
		
		check[x][y] = true;
    	cnt++;
    	System.out.println("x="+x+",y="+y+",cnt="+cnt);
		// 探索下一步(沒有回頭路)
		findPath(threshold,rows,cols, x+1, y);	// 向上
		findPath(threshold,rows,cols, x, y+1);	// 向左
	}
	
	public static boolean checkPath(int x,int y,int threshold) {
		int sum = 0;
		String strx = String.valueOf(x);
		for (int i = 0; i < strx.length(); i++) {
			sum += (strx.charAt(i)-'0');
		}
		
		String stry = String.valueOf(y);
		for (int i = 0; i < stry.length(); i++) {
			sum += (stry.charAt(i)-'0');
		}
		if (sum<=threshold) {
			return true;
		}else {
			return false;
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MovingCount movingCount = new MovingCount();
		// 21
		System.out.println(movingCount.movingCount(5, 10, 10));
		
	}

}
